home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / p_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  3.0 KB  |  128 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  p_heap.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PAIRING_HEAP_H
  17. #define LEDA_PAIRING_HEAP_H
  18.  
  19. #include<LEDA/basic.h>
  20.  
  21. // Implementation following John T. Stasko and Jeffrey Scott Vitter
  22. // ( Communications of the ACM   March 1987 Volume 30 Number 3   S. 234-240 )
  23. //
  24. // by Markus Neukirch   (1992)
  25.  
  26. class ph_item
  27. {
  28.   friend class pairing_heap;
  29.   friend class p_heap;
  30.   friend class p_aux_heap;
  31.  
  32.         GenPtr key;
  33.         GenPtr inf;
  34.  
  35.         ph_item* parent;
  36.         ph_item* l_child;
  37.         ph_item* r_child;
  38.  
  39.  
  40.         ph_item(GenPtr k,GenPtr i)
  41.         { parent = l_child = r_child=nil;
  42.           key=k;
  43.           inf=i;
  44.          }
  45.  
  46.        ~ph_item()       {} 
  47.         
  48.   LEDA_MEMORY(ph_item)
  49.         
  50. };
  51.  
  52.  
  53. class p_heap
  54. {
  55.         
  56.         ph_item* head;
  57.         int item_count;
  58.         void do_copy(ph_item*,ph_item*,bool);
  59.         void copy_sub_tree(ph_item*, ph_item*);
  60.         void clear_sub_tree(ph_item*);
  61.         ph_item* new_ph_item(GenPtr,GenPtr);
  62.  
  63.         virtual int cmp(GenPtr x, GenPtr y) const {return compare (x,y);}
  64.  
  65.         virtual void print_key(GenPtr)  const {}
  66.         virtual void print_inf(GenPtr)  const {}
  67.         virtual void clear_key(GenPtr&)  const {}
  68.         virtual void clear_inf(GenPtr&)  const {}
  69.         virtual void copy_key(GenPtr&)   const {}
  70.         virtual void copy_inf(GenPtr&)   const {}
  71.  
  72.         virtual int  int_type() const { return 0; }
  73.  
  74. protected:
  75.  
  76.         //ph_item* comparison_link(ph_item*,ph_item*);
  77.  
  78.         ph_item* twopass(ph_item*);
  79.         ph_item* multipass(ph_item*);
  80.  
  81.         ph_item* item(void* p) const { return (ph_item*)p; }
  82.  
  83.         
  84. public:
  85.         p_heap()        { item_count=0; }
  86.  
  87.         p_heap(int)     { error_handler(1,"no p_heap(int) constructor");}
  88.         p_heap(int,int) { error_handler(1,"no p_heap(int,int) constructor");}
  89.  
  90.         p_heap(const p_heap&);
  91.         p_heap& operator=(const p_heap&);
  92.  
  93. virtual ~p_heap() { clear(); }
  94.  
  95.  
  96.         ph_item* insert(GenPtr,GenPtr);
  97.  
  98.         ph_item* find_min() const { return head; }
  99.  
  100.         void decrease_key(ph_item*,GenPtr);
  101.         void delete_min_multipass();
  102.         void delete_min_twopass();
  103.  
  104.         void del_min() { delete_min_twopass(); }
  105.  
  106.         GenPtr key(ph_item* x) const {return x->key;}
  107.         GenPtr inf(ph_item* x) const {return x->inf;}
  108.  
  109.  
  110.         void change_inf(ph_item* x,GenPtr inf)
  111.                 {clear_inf(x->inf);copy_inf(inf);x->inf=inf;}
  112.         void del_item(ph_item* x)
  113.                 {decrease_key(x,head->key);delete_min_twopass();}
  114.  
  115.         void clear ();
  116.         
  117.         int  size() const  { return item_count; }
  118.         int  empty() const { return item_count>0; }
  119.  
  120.         // iteration (not yet implemented)
  121.  
  122.         ph_item* first_item()        const { return 0; }
  123.         ph_item* next_item(ph_item*) const { return 0; }
  124.  
  125. };      
  126.  
  127. #endif
  128.